1. Field of the Invention
The present invention relates to the determination of the arc length of a curve and, more particularly, to the determination of the arc length of a curve incorporated into an imaging system.
2. Description of the Related Art
The determination of the arc length of a curve is a necessary determination in many computer-aided-design and computer-graphics applications. For example, when patterns are positioned along a curve, the arc length of the curve must be determined. The construction of dashed lines is a common application since arc lengths are commonly used to determine when to start and stop a dash. Page-description languages such as Interpress and Post-Script allow a user to set arbitrary-patterns for lines and curves, thus making the determination of arc length a requirement for the imaging system.
The length of a line having any orientation is given by the well-known expression, ##EQU1## where 1 is the length of the line, x is the projection of the line on the .sub.x -axis, i.e., the difference of the x coordinates of the end points of the line, and y is the projection of the line on the .sub.y -axis, i.e., the difference of the .sub.y -coordinates of the end points of the line.
The length of a circular arc is given by the well-known expression EQU l=r a (2)
where 1 is the length of the arc, r is the radius of the arc and a is the angle of the arc in radians.
In accordance with the above-expressions, simple algebraic formulas are available for determinations of the arc length of lines and circular arcs. However, there is no simple algebraic formula for the arc length of more general curves such as arbitrary conics and cubics. In the case of such general curves, the structure of the curve is commonly segmented into small sections. Each section is then approximated by a line, and equation (1) is applied to yield an approximate length. The approximated lengths for all of the segments are added to yield the approximate length of the curve.
The above-described segmentation and length approximation requires knowledge of the precise manner in which the curve is to be subdivided. The ability and ease of the subdivision varies in accordance with the particular type of curve whose length is being approximated. In addition, in view of the necessity of subdividing the curve and calculating the square root of the sum of the squares of the line projections on the x and y axes, significant cost is incurred in determining the arc lengths. Further, the approximated arc length is determined only at the subdivision point.
One technique has been proposed to determine the approximate arc length of a curve. The technique calculates the approximate arc length during the curve generation and rendering process. For example, in computer graphics, curves are rendered as a set of pixels on a grid. Pixels which are intersected by the ideal curve are illuminated or inked. Various curve generation algorithms have been developed for determining which pixels should be selected as one moves along the ideal curve. A sequence of corresponding moves along the pixel grid results. FIG. 1 provides an illustration of a pixel grid 10 having an ideal curve 12 located thereon. A sequence of corresponding moves 14 along the pixel grid 10 are illustrated. The illuminated pixels determined to be selected during movement along curve 12 are shown by reference numeral 16.
In order to generate a continuous curve using the above-described technique, each step along the pixel grid 10 is limited to one of the eight directions illustrated in FIG. 2, each of the directions corresponding to the eight immediate neighbors of an individual pixel. In FIG. 2, the pixel is illustrated by the central dot 18 while the eight directions are illustrated by arrows 20. The pixel/grid motions 14 for the curve 12 shown in FIG. 1 are generated and are used as straight-line approximations to the curve 12. If a step in the curve generation is left, right, up or down, one pixel width is added to the curve length as the step is taken. If, however, a diagonal step is taken, a value of 1.414, i.e., the square root of 1.sup.2 +1.sup.2, times the pixel width is added to the curve length.
The above-described technique automatically performs the subdivision of the curve, thus incurring no additional costs. Because only two possible segment lengths, i.e., one pixel width or 1.414 times the pixel width, can be precomputed, no square root calculations are required. The technique determines the arc length for each pixel step, the pixel step being as fine as one is able to draw.
One problem resulting from the above-described technique is that the accuracy of the determination is limited. The computed arc length is equal to the length of a sequence of horizontal, vertical and diagonal lines leading from the start point of the curve to the end point of the curve. FIG. 3 illustrates a reordering of the pixel steps 14 performed for the curve 12 so that all of the steps in a given direction are grouped together. As illustrated in FIG. 3, the computed length deviates significantly from the actual length of the curve.